package sh.map;

public class HashMap<K, V> implements Map<K, V> {

    Entry[] table = null;  // 指向哈希表的引用变量
    int size = 0;   // 哈希表的大小, 即哈希表中有多少个键值对
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  // 默认的初始容量
    static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认的加载因子

    public HashMap() {
        this.table = new Entry[DEFAULT_INITIAL_CAPACITY];
    }

    @Override
    public V get(K key) {
        // 计算key的哈希值
        int hashCode = getHashCode(key);
        // 计算索引
        int index = hashCode % table.length;
        // 判断索引位置是否为空，如果不为空则遍历链表查找key值相同的节点
        // 情况1、索引位置为空，则直接返回null
        Entry entry = null;
        if (table[index] != null) {
            Entry currentEntry = table[index];
            while (currentEntry != null) {
                if (currentEntry.hash == key.hashCode() && (currentEntry.key.equals(key))) {
                    // 情况2、发生了冲突，但是找到了key值相同的节点，则返回value
                    entry = currentEntry;
                    break;
                }
                currentEntry = currentEntry.next;
            }

        }
        // 情况3：循环完了链表都没有找到key值相同的节点，则返回null
        return entry == null ? null : (V) entry.value;
    }

    @Override
    public V put(K key, V value) {
        // 计算key的哈希值
        int hashCode = getHashCode(key);
        // 计算索引
        int index = hashCode % table.length;
        // 判断索引位置是否为空，如果不为空则遍历链表查找key值相同的节点并更新value
        // 情况1：索引位置为空，则在索引位置插入新的节点
        if (table[index] == null) {
            Entry<K, V> kvEntry = new Entry<>(key, value, null, hashCode);
            table[index] = kvEntry;
            size++;
            // 判断是否需要扩容
//            if(size > table.length * DEFAULT_LOAD_FACTOR){
//                resize();
//            }
        } else {
            // 情况2：索引位置不为空，则判断是否发生了hash冲突
            // 发生hash冲突，遍历链表查找key值相同的节点并更新value
            Entry entry = table[index];   // 链表的头节点
            while (entry != null) {
                // 比较hash码和key值是否相等，如果都相同则更新value
                if (entry.hash == key.hashCode() && (entry.key.equals(key))) {
                    entry.value = value;  // 使用新的value
                    return value;  // 返回旧的value
                }
                // 下一个
                entry = entry.next;
            }
            // 情况3：索引位置不为空，并且没有发生hash冲突
            // 发生冲突并且没有找到相同的key，则在链表头部插入新的节点
            Entry<K, V> kvEntry = new Entry<>(key, value, table[index], hashCode);
            table[index] = kvEntry;
            size++;
            // 判断是否需要扩容
//            if(size > table.length * DEFAULT_LOAD_FACTOR){
//                resize();
//            }
        }

        return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("{ ");
        for (int i = 0; i < table.length; i++) {
            if (table[i] != null) {
                sb.append(table[i].toString());
                sb.append(", ");
            }
        }
        if (sb.length() > 2)
            sb.delete(sb.length() - 2, sb.length());
        sb.append(" }");

        return sb.toString();
    }

    private int getHashCode(K key) {
        return key.hashCode();
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    // 链表中的节点
    class Entry<K, V> implements Map.Entry<K, V> {

        K key;
        V value;
        Entry<K, V> next;
        int hash;

        public Entry(K key, V value, Entry<K, V> next, int hash) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.hash = hash;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public String toString() {
            if (next != null) {
                return "Entry{" +
                        "key=" + key +
                        ", value=" + value +
                        ", next=" + next +
                        ", hash=" + hash +
                        '}';
            }
            return "Entry{" +
                    "key=" + key +
                    ", value=" + value +
                    ", hash=" + hash +
                    '}';
        }
    }

//    Entry<K, V>[] table = null;  // 只是一个数组引用，指向数组开头
//    int size = 0;
//
//    public HashMap() {
//        table = new Entry[16];
//    }
//
//
//    /**
//     * 1、通过 key 算出 hash 值
//     * 2、通过 hash 值取模找到数组下标
//     * 3、判断数组下标是否为空，如果为空，则直接插入
//     * 4、如果不为空，则判断 key 是否相同，如果相同，则覆盖 value
//     *
//     * @param key
//     * @param value
//     * @return
//     */
//    @Override
//    public V put(K key, V value) {
//        int index = hash(key);  // 算出下标
//        Entry<K, V> entry = table[index];  // 取出数组下标
//        // 如果不是空
//        if (entry == null) {
//            table[index] = new Entry<K, V>(key, value, index, null);
//            size++;
//        } else {  // 不是空
//            //                   entry的next直接指向上一个
//            table[index] = new Entry<K, V>(key, value, index, entry);
//        }
//        return table[index].getValue();
//    }
//
//    @Override
//    public V get(K key) {
//        int index = hash(key);
//        Entry<K, V> entry = findValue(table[index], key);
//        if (entry != null) {
//            return entry.getValue();
//        }
//        return null;
//    }
//
//
//    /**
//     * 根据key查找 链表中是否有 key相同的节点
//     *
//     * @param entry
//     * @param k
//     * @return
//     */
//    public Entry<K, V> findValue(Entry<K, V> entry, K k) {
//        if (k.equals(entry.getKey()) || k == entry.getKey()) {
//            return entry;
//        } else {
//            if (entry.next != null) {
//                return findValue(entry.next, k);
//            }
//        }
//        return null;
//    }
//
//    // hash  =    17   10001       19   10011     21   10101
//    // length-1=  15   01111            01111          01111
////     &            00001            00011          00101
//
//    private int hash(K key) {
//        // int index = key.hashCode() & (table.length - 1);
//        int index = key.hashCode() % 16;
//        index = index >= 0 ? index : -index;
//        return index;
//    }
//
//    @Override
//    public int size() {
//        return size;
//    }
//
//    @Override
//    public boolean isEmpty() {
//        return table.length == 0;
//    }
//
//    // 节点
//    class Entry<K, V> implements Map.Entry<K, V> {
//        K k;
//        V v;
//        int index;
//        Entry<K, V> next;
//
//        public Entry(K k, V v, int index, Entry<K, V> next) {
//            this.k = k;
//            this.v = v;
//            this.index = index;
//            this.next = next;
//
//        }
//
//        @Override
//        public K getKey() {
//            return k;
//        }
//
//        @Override
//        public V getValue() {
//            return v;
//        }
//
//    }

}
